import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        QuickSort q = new QuickSort();
        int[] a = new int[]{3,2,3,1,2,4,5,5,6};
        q.quickSort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
    public void quickSort(int[] a ,int start,int end){
        if (start>=end)
            return;
        int p = a[start],l = start, r = end;
        while (l<r){
            while(l < r && a[r]>=p)
                r -=1;
            a[l] = a[r];
            while(l < r && a[l] < p)
                l +=1;
            a[r] = a[l];
        }
        a[l] = p;
        quickSort(a,start,l-1);
        quickSort(a,l+1,end);
    }






//    public void quickSort(int[] a,int low,int high){
//        if (low>=high)
//            return;
//        int p = a[low],l = low,h = high,now = low;
//        boolean flag = true;
//        while (l<=h){
//            if (flag){
//                if (a[h]<p){
//                    a[now] = a[h];
//                    now = h;
//                    h--;
//                    flag = false;
//                }else {
//                    h--;
//                }
//            }else{
//                if (a[l]>p){
//                    a[now] = a[l];
//                    now = l;
//                    l++;
//                    flag = true;
//                }else l++;
//            }
//        }
//        a[now] = p;
//        quickSort(a,low,now-1);
//        quickSort(a,now+1,high);
//    }
}
